package com.Questions.DP;

import java.util.*;
/**
 * 完全平方数
 */
public class leetcode279 {
    public int numSquares(int n) {
        int[] nums=new int[101];
        int[] dp=new int[n+1];
        Arrays.fill(dp,-1);
        for(int i=1;i<=100;++i){// 下标从1 开始
            nums[i]=i*i;
            if(i*i<=n){
                dp[i*i]=1;// 一个完全平方数就能组成n
            }
        }
        for(int i=2;i<=n;++i){
            if(dp[i]!=1){
                int min=50000;
                for(int j=1;j<=100;j++){//找到能组成它的最少个数
                    if(i-nums[j]<1){
                        break;
                    }
                    min=Math.min(min,dp[i-nums[j]]);// 这个地方犯了一个愚蠢的错误 将j写成了i
                }
                dp[i]=min+1;
            }
        }
        return dp[n];
    }
}
